UVa/11590 - Prefix lookup/11590.cpp

   1 //WA!
   2 using namespace std;
   3 #include <algorithm>
   4 #include <iostream>
   5 #include <iterator>
   6 #include <sstream>
   7 #include <fstream>
   8 #include <cassert>
   9 #include <climits>
  10 #include <cstdlib>
  11 #include <cstring>
  12 #include <string>
  13 #include <cstdio>
  14 #include <vector>
  15 #include <cmath>
  16 #include <queue>
  17 #include <deque>
  18 #include <stack>
  19 #include <list>
  20 #include <map>
  21 #include <set>
  22
  23 #define D(x) cout << #x " is " << (x) << endl
  24
  25 typedef unsigned long long Int;
  26 const int BUFSIZE = 256;
  27 char buf[BUFSIZE];
  28
  29 int M;
  30 map<string, Int> ans;
  31
  32 struct node{
  33   node * left, * right;
  34   bool end; //is this node a complete prefix?
  35   node(bool e) : end(e) {
  36     left = right = NULL;
  37   }
  38 };
  39
  40 //not used, because I love to waste memory (It makes me feel dangerous)
  41 void clean(node * n){
  42   if (n == NULL) return;
  43   clean(n->left); clean(n->right);
  44   delete n;
  45 }
  46
  47 Int f(string s, node * n){ //s = string built so far, n = the node we are standing at
  48   Int left = 0, right = 0;
  49   if (n->left != NULL){
  50     left = f(s + "0", n->left);
  51   }
  52   if (n->right != NULL){
  53     right = f(s + "1", n->right);
  54   }
  55   if (n->end){
  56     Int x = ((1ULL) << (M - s.size())) - 1;
  57     if (M - s.size() == 64){
  58       x = ~(0ULL);
  59     }
  60     ans[s] = x - left + 1 - right;
  61   }
  62   Int ret = 0;
  63   if (n->end){
  64     ret = ans[s];
  65   }
  66   return ret + left + right;
  67 }
  68
  69 int main(){
  70   int n;
  71   while (scanf("%d %d\n", &n, &M)==2 && !(n == 0 && M == 0)){
  72     ans.clear();
  73     node * root = new node(true);
  74     while (n--){
  75       fgets(buf, BUFSIZE, stdin);
  76       node * cur = root;
  77       for (int i=0; ; ++i){
  78         if (buf[i] == '*'){
  79           cur->end = true;
  80           break;
  81         }
  82         if (buf[i] == '0'){
  83           if (cur->left == NULL) cur->left = new node(false);
  84           cur = cur->left;
  85         }else if (buf[i] == '1'){
  86           if (cur->right == NULL) cur->right = new node(false);
  87           cur = cur->right;
  88         }
  89       }
  90     }
  91
  92     f("", root);
  93
  94     int K;
  95     scanf("%d\n", &K);
  96     while (K--){
  97       fgets(buf, BUFSIZE, stdin);
  98       buf[strlen(buf)-2] = '\0'; //delete *\n
  99       Int t = ans[string(buf)];
 100       assert(t >= 0);
 101       printf("%llu\n", t);
 102     }
 103
 104     fgets(buf, BUFSIZE, stdin); //empty line
 105     puts("");
 106   }
 107   return 0;
 108 }